package com.foxzzz.back.tracking;

import java.util.*;

public class Solution37 {
   
    public void solveSudoku(char[][] board) {
        Set<Character> leftSet = new HashSet<>();
        Collections.addAll(leftSet, '1', '2', '3', '4', '5', '6', '7', '8', '9');
        int blank = 0;
        char[][] oper=new char[board.length][board[0].length];
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[i].length; j++) {
                oper[i][j]=board[i][j];
                if (board[i][j] == '.')
                    blank++;
            }

        sudo(board,oper,0, blank, leftSet);
    }

    public void sudo(char[][] board,char[][] oper,int index, int blank, Set<Character> leftSet) {

        if (blank == -1 || index == 81) {
            for (int i = 0; i < board.length; i++)
                for (int j = 0; j < board[i].length; j++) {
                   board[i][j]= oper[i][j];
                }
            return;
        }
        int x = index % oper.length;
        int y = index / oper.length;
        Set<Character> set = new HashSet<>(leftSet);
        if (oper[x][y] == '.') {
            //纵向去数字
            for (int i = 0; i < oper[x].length; i++) {
                if (oper[x][i] != '.') {
                    set.remove(oper[x][i]);
                }
            }
            //横向去数字
            for (int i = 0; i < oper.length; i++) {
                if (oper[i][y] != '.') {
                    set.remove(oper[i][y]);
                }
            }
            //9格去数字
            for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++)
                for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++) {
                    if (oper[i][j] != '.') {
                        set.remove(oper[i][j]);
                    }
                }

            for (Character character : set) {
                oper[x][y] = character;
                sudo(board,oper, index + 1, blank - 1, new HashSet<>(leftSet));
                oper[x][y] = '.';
            }
        } else {
            sudo(board,oper, index + 1, blank, new HashSet<>(leftSet));
        }


    }

    private char[][] genTestCast(String test, int w, int h) {
        char[][] result = new char[w][h];
        String strs[] = test.replace("[", "").replace("]", "").replace("\"", "").split(",");
        for (int i = 0; i < strs.length; i++) {
            int y = i / h;
            int x = i % w;
            result[x][y] = strs[i].charAt(0);
        }
        return result;
    }

    private void pringCast(char[][] p) {
        for (int i = 0; i < p.length; i++) {
            for (int j = 0; j < p[i].length; j++) {
                System.out.print(p[j][i] + "|");
            }
            System.out.println("");
        }
    }

    public static void main(String[] args) {
        String s = "[[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"],[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"],[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"],[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"],[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"],[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"],[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"],[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"],[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]";
        Solution37 s37 = new Solution37();
        char[][] testCast = s37.genTestCast(s, 9, 9);
        s37.solveSudoku(testCast);
        s37.pringCast(testCast);
    }
}
